#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

void mysort(vector<int>& nums, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int l = left - 1, r = right + 1;
	int mid = left + (right - left) / 2;
	int key = nums[mid];
	int cur = left;
	while (cur < r)
	{
		if (nums[cur] < key)
		{
			swap(nums[++l], nums[cur++]);
		}
		else if (nums[cur] > key)
		{
			swap(nums[--r], nums[cur]);
		}
		else
		{
			cur++;
		}
	}
	mysort(nums, left, l);
	mysort(nums, r, right);
}
vector<int> tmp;
void msort(vector<int>& nums, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	msort(nums, left, mid);
	msort(nums,mid + 1, right);
	int cur1 = left, cur2 = mid + 1, cur = left;
	while (cur1 < mid + 1 && cur2 < right + 1)
	{
		if (nums[cur1] < nums[cur2])
		{
			tmp[cur++] = nums[cur1++];
		}
		else
		{
			tmp[cur++] = nums[cur2++];
		}
	}
	while (cur1 < mid + 1)
	{
		tmp[cur++] = nums[cur1++];
	}
	while (cur2 < right + 1)
	{
		tmp[cur++] = nums[cur2++];
	}
	for (int i = left; i <= right; i++)
	{
		nums[i] = tmp[i];
	}

}
void adjustup(vector<int>&nums, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (nums[child] > nums[parent])
		{
			swap(nums[child], nums[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}
void adjustdown(vector<int>& nums, int maxsize, int parent)
{
	int child = parent * 2 + 1;
	while (child<=maxsize)
	{
		if ((child + 1) <= maxsize && nums[child + 1] > nums[child])
		{
			child++;
		}
		if (nums[parent] < nums[child])
		{
			swap(nums[parent], nums[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void hsort(vector<int>&nums,int left,int right)
{
	for (int i = left; i <= right; i++)
	{
		make_heap(nums.begin() + i, nums.begin() + right + 1);
	}
}

int main()
{
	
	vector<int> nums = { 8,4,1,7,9,2,5,3,6,0 };
	for (int i = 1; i < nums.size()-1; i++)
	{
		adjustup(nums, i);
	}
	for (int i = nums.size()-1; i > 0; i--)
	{
		swap(nums[0], nums[i]);
		adjustdown(nums, i-1, 0);
	}
	tmp.resize(nums.size());
	//msort(nums, 0, nums.size() - 1);
	for (auto num : nums)
	{
		cout << num <<" ";
	}
	cout << endl;
	return 0;
}